#include "link.h"
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#if 0
//在链表头之前插入
STU * insert_link(STU *head, STU tmp)
{
	//1.从堆区申请一个待插入的节点空间
	STU* pi = (STU*)calloc(1, sizeof(STU));// pi指针接返回的指针
	if (pi == NULL)//申请失败
	{
		perror("calloc");
		return head;
	}
	//2.将tmp的值 赋给*pi
	*pi = tmp;
	pi->next = NULL;
	//3.将pi插入到链表中
	if (head == NULL)//链表不存在
	{
		head = pi;
		
	}
	else//链表存在
	{
		//1让pi指向旧的头
		pi->next = head;
		//2.head指向新的头
		head = pi;
	}
	return head;
}
#endif 

#if 0
//在链表尾部插入
STU* insert_link(STU* head, STU tmp)
{
	//1.从堆区申请一个待插入的节点空间
	STU* pi = (STU*)calloc(1, sizeof(STU));
	if (pi == NULL)
	{
		perror("calloc");
		return head;
	}
	//2.将tmp的数据 赋值给 *pi
	*pi = tmp;
	pi->next = NULL;
	//3.将节点插入链表尾部
	if (head == NULL)//链表不存在,pi就是第一个节点
	{
		head = pi;

	}
	else//链表存在
	{
		//1寻找尾节点
		STU* pb = head;
		while (pb->next != NULL)
		{
			pb = pb->next;
		}
		//2.尾结点连接pi
		pb->next = pi;
		pi->next = NULL;
	}
	return head;
}
#endif 
//链表的有序插入
STU* insert_link(STU* head, STU tmp)
{
	//1.从堆区申请一个待插入的节点空间
	STU* pi = (STU*)calloc(1, sizeof(STU));
	if (pi == NULL)
	{
		perror("calloc");
		return head;
	}
	//2.将tmp的数据 赋值给 *pi
	*pi = tmp;
	pi->next = NULL;
	//3.插入节点
	if (head == NULL)//链表不存在,pi就是第一个节点
	{
		head = pi;

	}
	else//链表存在
	{
		//1.寻找插入点
		STU* pb = head,*pf=head;
		while (pb->num<pi->num && pb->next!=NULL)
		{
			pf = pb;
			pb = pb->next;
		}
		//判断插入点情况
		if (pb->num >= pi->num)//如果以这个条件退出上面的循环，则头 中 插入
		{
			if (pb == head)//头前
			{
				pi->next = head;//指向旧的头
				head = pi;//赋值新的头
				return head;
			}
			else//中部插入
			{
				pf->next = pi;
				pi->next = pb;
				return head;
			}
		}
		else// 不以 pb->num >= pi->num退出循环，则就是pb->next=NULL。尾部插入
		{
			pb->next = pi;
			pi->next = NULL;
			return head;
		}
	}
	return head;
}
void print_link(STU* head)
{
	if (head == NULL)//链表不存在
	{
		printf("链表不存在\n");
	}
	else
	{
		STU* pb = head;//pb 用来移动
		while (pb != NULL)
		{
			printf("%d %s %f\n", pb->num, pb->name, pb->score);
			pb = pb->next;
		}
	}
}
STU* search_link(STU* head, char* name)
{
	//判断链表存在与否
	if (head == NULL)
	{
		printf("链表不存在\n");
		return NULL;
	}
	else //链表存在
	{
		STU* pb = head;
		// 遍历链表直到找到匹配的名称或到达链表末尾
		while (pb != NULL && strcmp(pb->name, name) != 0)
		{
			pb = pb->next;
		}
		// 如果 pb 为 NULL，说明链表遍历完了仍未找到，或者链表本身就是 NULL
		if (pb == NULL)
		{
			return NULL;
		}
		// 否则，返回找到的节点
		return pb;
	}
}
STU* detele_link(STU* head, char* name)
{
	//判断链表是否存在
	if (head == NULL)//不存在
	{
		printf("链表不存在\n");
		return head;
	}
	else//存在
	{
		//寻找删除点
		STU* pb = head, * pf = head;
		while (pb->next != NULL && strcmp(pb->name, name) != 0)
		{
			pf = pb;
			pb = pb->next;
		}
		if (strcmp(pb->name, name) == 0)//找到
		{
			//判断删除点的位置
			if (pb == head)//头
			{
				head = pb->next;
				free(pb);
			}
			else//非头
			{
				pf->next = pb->next;
				free(pb);
			}
			printf("已删除%s的相关内容\n", name);
			return head;
		}
		else //没找到
		{
			printf("link no or name not found\n");
			return head;
		}

	}
	return head;
}
STU* free_link(STU* head)
{
	//判断链表是否存在
	if (head == NULL)//不存在
	{
		printf("链表不存在\n");
		return head;
	}
	else//存在
	{
		STU* pb = head;
		while (pb != NULL)
		{
			head = pb->next;//把head 后移
			free(pb);//释放当前
			pb = head;//pb 后移
		}
		printf("链表已经释放\n");
		return head;
	}
	return head;
}
STU* reverse_link(STU* head)
{
	//判断链表是否存在
	if (head == NULL)//不存在
	{
		printf("链表不存在\n");
		return head;
	}
	else//存在
	{
		STU* pb = NULL, * pr = NULL;
		//pb保存head->next 因为head->next会置空
		pb = head->next;
		head->next = NULL;//头变尾
		while(pb!=NULL)
		{
			//pr保存pb->next 因为 pb->next 指向head
			pr = pb->next;
			//pb->next 指向head 因为要逆转方向
			pb->next = head;
			//移动 head  和 pb  进行循环
			head = pb;
			pb = pr;
		}
		return head;
	}
	return head;//无用，只是保证函数每段都有返回值
}
STU* sort_link(STU* head)
{
	if (head == NULL || head->next == NULL) // 如果链表为空或只有一个结点，无需排序
		return head;

	STU* p_i = head;
	while (p_i->next != NULL)
	{
		STU* p_min = p_i;
		STU* p_j = p_i->next;

		while (p_j != NULL)
		{
			if (p_j->score < p_min->score) // 找到更小的结点
				p_min = p_j;
			p_j = p_j->next;
		}

		if (p_min != p_i) // 如果需要交换
		{
			// 交换 p_i 和 p_min 的 next 指针
			STU* tmp = p_min->next;
			p_min->next = p_i->next;
			p_i->next = tmp;

			// 如果 p_i 是头结点，需要更新头结点
			if (head == p_min)
				head = p_i;
		}
		p_i = p_i->next;
	}
	return head;
}